import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-06
 * Time: 22:47
 */
class Solution {

    /**
     *  方法一: 枚举 + 排序  + 前缀和 +二分查找
     *  范围为 [0, max]
     *  对于 每个 x 都进行二分查找, 找它在 数组中的位置, 然后就可以使用前缀和更方便的 求出 sum
     * @param arr
     * @param target
     * @return
     */
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int dist = Integer.MAX_VALUE;
        int left = 0;
        int max = arr[0];
        int len = arr.length;
        int[] prefix = new int[len];
        int ans = 0;
        prefix[0] = arr[0];
        for (int i = 1; i < len; i++) {
            prefix[i] = prefix[i-1] + arr[i];
            max = Math.max(max, arr[i]);
        }
        for (int i = 0; i <= max;i++) {
            int pos = binarySearch(arr, i);
            int sum = 0;
            if (pos < 0) {
                sum = len * i;
            } else {
                sum = prefix[pos] + (len-1-pos) * i;
            }
            if (Math.abs(sum-target) < dist) {
                ans = i;
                dist = Math.abs(sum-target);
            }
        }
        return ans;
    }


    public int binarySearch(int[] arr, int val) {
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = ((right-left+1) >> 1) + left;
            if (arr[mid] > val) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return arr[right] <= val ? right : right - 1;
    }


    /**
     *  方法二: 双层二分查找
     *  因为最接近的那两个一定是挨着的, 一个大于 target, 一个小于 target
     *  所以我们直接找到 最接近并且小于 target 的那个值 x, 然后再比较与 x+1 相比哪个的和更接近 target
     *  注意如果最后相等, 那么返回的是小的那个
     * @param arr
     * @param target
     * @return
     */
    public int findBestValue2(int[] arr, int target) {
        Arrays.sort(arr);
        int dist = Integer.MAX_VALUE;
        int max = arr[0];
        int len = arr.length;
        int[] prefix = new int[len];
        int ans = 0;
        prefix[0] = arr[0];
        for (int i = 1; i < len; i++) {
            prefix[i] = prefix[i-1] + arr[i];
            max = Math.max(max, arr[i]);
        }
        int left = 0;
        int right = max;
        while (left < right) {
            int mid = ((right-left+1) >> 1) + left;
            int sum = getSum(arr, mid, prefix);
            if (sum > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        int sum1 = getSum(arr, right, prefix);
        int sum2 = getSum(arr, right+1, prefix);
        // 注意最后相等时返回小的那个
        return Math.abs(sum1-target) <= Math.abs(sum2-target) ? right : right + 1;
    }


    public int getSum(int[] arr,int  val, int[] prefix) {
        int len = arr.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = ((right-left+1) >> 1) + left;
            if (arr[mid] > val) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }

        int pos = arr[right] <= val ? right : right - 1;
        int sum = 0;
        if (pos < 0) {
            sum = len * val;
        } else {
            sum = prefix[pos] + (len-1-pos) * val;
        }
        return sum;
    }
}
